P3503 [POI2010]KLO-Blocks

首先可以知道一个区间满足条件的必要条件是该区间的平均数大于等于 kk

进一步可以发现这是一个充要条件。因为大于 kk 的数一定能填补到小于 kk 的数。

记一个合法的区间为 [l,r][l,r]sumsumaa 的前缀和。

sum[r]sum[l1]k×(rl+1)sum[r]-sum[l-1] \ge k \times (r-l+1)

sum[r]k×rsum[l1]k×(l1)sum[r]- k \times r \ge sum[l-1] - k \times (l-1)

si=sum[i]k×is_i=sum[i]-k \times i

则有 srsl10s_r-s_{l-1} \ge 0

我们可以Θ(n)\Theta(n)处理出ss ,然后就可以用单调栈求解了。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 1000000;
int n , m , k , a[ MAXN + 5 ] , Top , Stk[ MAXN + 5 ]; 
long long sum[ MAXN + 5 ];

int main( ) {
//  freopen("blocks.in","r",stdin);
//  freopen("blocks.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&a[ i ]);
	while( m -- ) {
		scanf("%d",&k);
        for( int i = 1 ; i <= n ; i ++ )
            sum[ i ] = sum[ i - 1 ] + a[ i ] - k;
        
        int Ans = 0;
        Top = 0; Stk[ ++ Top ] = 0;
        for( int i = 1 ; i <= n ; i ++ )
            if( sum[ i ] < sum[ Stk[ Top ] ] ) Stk[ ++ Top ] = i;
        for( int i = n ; i >= 1 ; i -- ) {
            while( Top && sum[ i ] - sum[ Stk[ Top ] ] >= 0 ) Top --;
            Ans = max( Ans , i - Stk[ Top + 1 ] );
        }
        printf("%d ",Ans);
	} 
	return 0;
}